package com.maltys.dp.backpack;

/**
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的⽅法可以爬到楼顶呢？
 * 注意：给定 n 是⼀个正整数。
 *
 * @author malty
 * @link <a href="https://leetcode.cn/problems/climbing-stairs/description/">爬楼梯</a>
 */
public class ClimbStairs {
    public static void main(String[] args) {
        ClimbStairs climbStairs = new ClimbStairs();
        int stairs = climbStairs.climbStairs(3);
        System.out.println(stairs);
    }

    public int climbStairs(int num) {
        int[] dp = new int[]{1, 2};
        if (num < 3) {
            return dp[num - 1];
        }
        for (int i = 3; i <= num; i++) {
            int tmp = dp[1];
            dp[1] = dp[0] + dp[1];
            dp[0] = tmp;
        }
        return dp[1];
    }
}
